package CodeTop.hash;

import java.util.HashMap;
import java.util.Map;

public class A560 {
    //遍历同时存储哈希表，用于后续使用
    public int subarraySum1(int[] nums, int k) {
        int n=nums.length;
        //构造前缀数组
        int[] s=new int[n+1];
        for(int i=0;i<n;i++){
            s[i+1]=s[i]+nums[i];
        }
        //前缀和，出现次数
        Map<Integer,Integer>map=new HashMap<>(n+1);
        int res=0;
        for (int i : s) {
            //对于当前前缀和i,前面如果出现了前缀和x,且i-x=k,则该子数组成立
            res+=map.getOrDefault(i-k,0);
            //将当前值也加入哈希表
            map.put(i,map.getOrDefault(i,0)+1);
        }
        return res;
    }
    //优化，边构造前缀和边计算
    public int subarraySum2(int[] nums, int k) {
        int n=nums.length;
        Map<Integer,Integer>map=new HashMap<>(n+1);
        //前0个元素的前缀和=0，出现1次
        map.put(0,1);
        int res=0;
        //构造前缀数组
        int[] s=new int[n+1];
        for(int i=0;i<n;i++){
            s[i+1]=s[i]+nums[i];
       int j=s[i+1]-k;
       res+=map.getOrDefault(j,0);
   map.put(s[i+1],map.getOrDefault(s[i+1],0)+1);

        }
        return res;
    }

    //优化，由于线性，前面存储可舍弃
        public int subarraySum(int[] nums, int k) {
            int n=nums.length;
            Map<Integer,Integer>map=new HashMap<>(n+1);
            //前0个元素的前缀和=0，出现1次
            int s=0;
            map.put(0,1);
            int res=0;
            for (int num : nums) {
                s+=num;
                res+=map.getOrDefault(s-k,0);
                map.merge(s,1,Integer::sum);//Integer::sum 是合并函数，当 s 已经存在时，会将旧值和新值相加
            }
            return res;
        }
}
